package com.apkcore.bl;

public class _483最小好进制 {
    /**
     * n == k^(m-1)+k^(m-2)...k^1+k^0
     * n==k^(m-1)/(k-1)
     * 要求k尽可能的小
     * m最大值= log2(num)+1
     * https://leetcode-cn.com/problems/smallest-good-base/solution/er-fen-jian-ji-ming-liao-bu-dong-lai-da-7p4vc/
     */
    public String smallestGoodBase(String n) {
        //将字符串解析成long型数据
        long num = Long.parseLong(n);
        //对进行m的大小进行穷举（m含义是转换为k进制后1的个数）
        for(int m = (int)(Math.log(num + 1) / Math.log(2)); m >= 2; m--){
            //用二分法搜索对应的k,(k的含义是k进制)
            long left = 2, right = (long)Math.pow(num, 1.0 / (m-1)) + 1;
            while(left < right){
                long mid = left + (right - left) / 2, sum = 0;

                //等比数列求和
                for(int j = 0; j < m; j++)
                    sum = sum * mid + 1;

                if(sum == num)
                    return String.valueOf(mid);
                else if(sum < num)
                    left = mid + 1;
                else
                    right = mid;
            }
        }
        return String.valueOf(num - 1);
    }

    /**
     * https://leetcode-cn.com/problems/smallest-good-base/solution/bi-mian-er-fen-cha-zhao-de-jian-dan-javajie-fa-by-/
     */
    public String smallestGoodBase1(String n) {
        long N = Long.parseLong(n);
        for (int m = 59; m > 1; m--) {
            long k = (long) Math.pow(N, 1.0 / m);
            //不存在1进制，如果k<=1，直接下一次
            if (k <= 1)
                continue;
            long s = 0;
            for (int i = 0; i <= m; i++)
                s = s * k + 1;
            if (s == N)
                return String.valueOf(k);
        }
        return String.valueOf(N - 1);
    }
}
